package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/find-largest-value-in-each-tree-row/'>在每个树行中找最大值(Find Largest Value in Each Tree Row)</a>
 * <p>给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例1：
 *      输入: root = [1,3,2,5,3,null,9]
 *                  1
 *                /  \
 *               3    2
 *              / \    \
 *             5   3    9
 *      输出: [1,3,9]
 *
 * 示例2：
 *      输入: root = [1,2,3]
 *                  1
 *                /  \
 *               2    3
 *      输出: [1,3]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>二叉树的节点个数的范围是 [0,10^4]</li>
 *     <li>-2^31 <= Node.val <= 2^31 - 1</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/16 14:06
 */
public class LC0515FindLargestValueInEachTreeRow_M {

    static class Solution {
        public List<Integer> largestValues(TreeNode root) {
            List<Integer> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                int currLevelNodeMaxVal = Integer.MIN_VALUE;
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                    currLevelNodeMaxVal = Math.max(currLevelNodeMaxVal, currNode.val);
                }
                resList.add(currLevelNodeMaxVal);
            }
            return resList;
        }

        public List<Integer> largestValues2(TreeNode root) {
            List<Integer> resList = new ArrayList<>();
            dfs(root, 0, resList);
            return resList;
        }

        private void dfs(TreeNode currNode, int currLevel,List<Integer>resList) {
            if (currLevel == resList.size()) {
                resList.add(currNode.val);
            } else {
                resList.set(currLevel, Math.max(resList.get(currLevel), currNode.val));
            }
            if (currNode.left != null) {
                dfs(currNode.left, currLevel + 1, resList);
            }
            if (currNode.right != null) {
                dfs(currNode.right, currLevel + 1, resList);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(5);
        root1.left.right = new TreeNode(3);
        root1.right.right = new TreeNode(9);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);

        Solution solution = new Solution();
        System.out.println(solution.largestValues(root1));
        System.out.println(solution.largestValues(root2));
    }
}
